package cmk.lee.easy;

public class Leetcode_21 {
    /**
     * 将两个升序链表合并为一个新的 升序 链表并返回。
     * 新链表是通过拼接给定的两个链表的所有节点组成的。
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return val +"-"+ next;
        }
    }

    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        /*
        递归算法：
        举个栗子 比如: l1: 1-3-4
                     l2: 2-2-3
              排除对方为空的情况
              l1.val =1 < l2.val=2
              则比较 l1 = l1.next:3-4
                    l2:2-2-3
              结果   l1 = 3-4
                    l2 = 2-3
              如此递归，调用本方法求出两个ListNode中最小值，将其排除，l1=l1.next
              进而继续执行此方法
         */
        if (l1==null){
            return l2;
        }else if (l2==null){
            return l1;
        }else if(l1.val< l2.val){
           l1.next =  mergeTwoLists(l1.next,l2);
            return l1;

        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;

        }
    }

    public static void main(String[] args) {

        ListNode listNode03 = new ListNode(4);
        ListNode listNode02 = new ListNode(2,listNode03);
        ListNode listNode01 = new ListNode(1,listNode02);


        ListNode listNode05 = new ListNode(4);
        ListNode listNode04 = new ListNode(3,listNode05);
        ListNode listNode06 = new ListNode(1,listNode04);

        ListNode list = mergeTwoLists(listNode01,listNode06);

        System.out.println(list);
    }
}
